﻿#include <iostream>

static void infect(int* arr, const size_t xSize, const size_t ySize, const int x, const int y) {
    if (x < 0 || x >= xSize || y < 0 || y >= ySize || arr[x+y*xSize] != 1)
        return;

    arr[x+y*xSize] = 2;
    infect(arr, xSize, ySize, x - 1, y);
    infect(arr, xSize, ySize, x + 1, y);
    infect(arr, xSize, ySize, x, y - 1);
    infect(arr, xSize, ySize, x, y + 1);
}

static int getIslandCount(int* arr, const size_t xSize, const size_t ySize) {
    int count = 0;
    for (int x = 0; x < xSize; x++) {
        for (int y = 0; y < ySize; y++) {
            if (arr[x+y*xSize] == 1) {
                count++;
                infect(arr, xSize, ySize, x, y);
            }
        }
    }

    return count;
}

/**
 * 岛问题
 * [题目]
 * 一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，
 * 如果有一片1连在一起，这个部分叫做一个岛。
 * 求一个矩阵中有多少个岛?
 * [举例]
 * 0 0 1 0 1 0
 * 1 1 1 0 1 0
 * 1 0 0 1 0 0
 * 0 0 0 0 0 0
 *
 * 这个矩阵中有三个岛.
 *
 * [进阶]
 * 如何设计一个并行算法解决这个问题?
 */
int main_Island()
{
#define X_SIZE 6
    int arr[][X_SIZE] = {
        {0, 0, 1, 0, 1, 0},
        {1, 1, 1, 0, 1, 0},
        {1, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0},
    };

    size_t ySize = sizeof(arr)/(sizeof(int)*X_SIZE);
    int islandCount = getIslandCount(*arr, X_SIZE, ySize);
    printf("%d\n", islandCount);
    return 0;
}